package 贪心;

import java.util.Arrays;

/**
 * 问题描述：
有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。
最优装载问题要求确定在装载体积不受限制的情况下，
将尽可能多的集装箱装上轮船。(意思就是在不超过载重量的情况下最多能装多少)
 *
 */
public class 最优子装载问题 {
	 
	public static int solution(int choice[],int maxValue) {
		int len =choice.length;
		return process(0,choice,maxValue,len);
	}
	/**
	 * 多叉树版本
	 * 排个序 
	 * 还可以 进行 剪枝操作!
	 */
	public static int process(int index,int choice[],int rest,int len) {
//		if(rest == 0)
//			return 1;
//		if(rest < 0) {
//			return 0;
//		}
		int ans = 0;
		for(int i = index;i < len;i++) {
			if(rest - choice[i] >= 0)
				ans = Math.max(ans, process(i + 1,choice,rest - choice[i],len) + 1);
		}
		return ans;
	}
	
	
	/**
	 * 二叉树版本
	 */
	
	public static int processTwo(int index,int choice[],int rest,int len) {
		//basecase
		if(index == len)
			return 0;
		int ans = 0;
		if(rest - choice[index] >= 0)
			ans = processTwo(index + 1,choice,rest - choice[index],len) + 1;
		return Math.max(ans, processTwo(index + 1,choice,rest,len));
		
	}
	// 直接将上面的  二叉树版本的回溯(递归) 改成 dp
	public static int dp(int choice[],int maxValue) {
		int len = choice.length;
		int dp [][] = new int [len + 1][maxValue + 1];
		for(int index = len - 1;index >= 0; index--) {
			for(int rest = 0;rest <= maxValue; rest++) {
				if(rest - choice[index] >=0 )
					dp[index][rest] = dp[index + 1][rest - choice[index]] + 1;
				dp[index][rest] = Math.max(dp[index][rest], dp[index + 1][rest]);
			}
		}
		return dp[0][maxValue];
	}
	
	/**
	 * 这种贪心 有什么 可讲的
	 */
	public static int greedy(int choice[],int maxValue) {
		Arrays.sort(choice);
		int sum = 0;
		int count = 0;
		int i = 0;
		while(true) {
			// 先判断 再 把 count ++ 不就行了
			sum += choice[i++];				
			if(sum > maxValue)
				break;
			
			  count++;
		}
		return count;
	}
	
 	
	public static void main(String []args) {
		int nums[] = {4,10,7,11,3,5,14,2};
		int c = 30;
		System.out.println(solution(nums,c));
		System.out.println(processTwo(0,nums,c,nums.length));
		System.out.println(dp(nums,c));
		System.out.println(greedy(nums,c));
	}
}
